|
In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add. ==Basic method== The method is based on the observation that, for a positive integer ''n'', we have : This may be easily implemented as the following recursive algorithm: Function exp-by-squaring(x, n ) if n < 0 then return exp-by-squaring(1 / x, - n ); else if n = 0 then return 1; else if n = 1 then return x ; else if n is even then return exp-by-squaring(x * x, n / 2); else if n is odd then return x * exp-by-squaring(x * x, (n - 1) / 2). Although not tail-recursive, this algorithm may be rewritten into a tail recursive algorithm by introducing an auxiliary function: Function exp-by-squaring(x, n) exp-by-squaring2(1, x, n) Function exp-by-squaring2(y, x, n) if n < 0 then return exp-by-squaring2(y, 1 / x, - n); else if n = 0 then return y; else if n = 1 then return x * y; else if n is even then return exp-by-squaring2(y, x * x, n / 2); else if n is odd then return exp-by-squaring2(x * y, x * x, (n - 1) / 2). The iterative version of the algorithm also uses a bounded auxiliary space, and is given by Function exp-by-squaring-iterative(x, n) if n < 0 then x := 1 / x; n := -n; if n = 0 then return 1 y := 1; while n > 1 do if n is even then x := x * x; n := n / 2; else y := x * y x := x * x; n := (n – 1) / 2; return x * y 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「exponentiation by squaring」の詳細全文を読む スポンサード リンク
|